package com.lw.leetcode.binary.b;

/**
 * Created with IntelliJ IDEA.
 * binay
 * LCP 12. 小张刷题计划
 *
 * @author liw
 * @version 1.0
 * @date 2022/5/15 12:16
 */
public class MinTime {

    public static void main(String[] args) {
        MinTime test = new MinTime();

        // 3
        int[] time = {1, 2, 3, 3};
        int m = 2;

        // 0
//        int[] time = {999, 999, 999};
//        int m = 4;

        int i = test.minTime(time, m);
        System.out.println(i);
    }

    public int minTime(int[] time, int k) {
        int length = time.length;
        int st = 0;
        int end = 0;
        for (int i : time) {
            end += i;
        }
        end /= k;
        while (st < end) {
            int m = st + ((end - st) >> 1);
            int sum = 0;
            int max = 0;
            int count = 1;
            for (int i = 0; i < length; i++) {
                int t = time[i];
                max = Math.max(max, t);
                sum += t;
                if (sum - max > m) {
                    count++;
                    max = t;
                    sum = t;
                }
            }
            if (count <= k) {
                end = m;
            } else {
                st = m + 1;
            }
        }
        return st;
    }

}
